First-in first-out memories resemble a queue, with a "head" which contains the oldest information and a "tail" which contains the most recent information. Last-in first-out memories, on the other hand, resemble a stack of cards where the "head" or "top of the stack" contains the most recent information and the "tail" or "bottom of the stack" contains the oldest information. In FIFO memories it is the oldest information that exits the queue first. In LIFO memories it is the most recent information that exits the stack first.
The most common design of FIFO/LIFO memories employs random access memories (RAMs) to store information, and counters to keep track of the RAM address of the "head" and "tail" of the stored information. This design, however, suffers several drawbacks. First, the delay from initiation of the read or write cycle to the data output or write operation includes both counter and memory decoder delays. Second, in LIFO operation, the RAM must first be read and written in one LIFO clock period and that presents problems in the RAM utilization; and third, asynchronous clocking of the head and tail can generate a requirement for simultaneous reading and writing of the RAM, which can force delay of the operations. A dual ported memory can solve the second and third drawbacks, but only at the expense of adding to the complexity of the memory system.
Another FIFO design technique uses a constant length shift register as a FIFO memory, writing the data in at one end, then shifting it out at the other. This avoids the need for a decoder, but introduces counter delays and a constant latency, or fall-through time. A LIFO may also be implemented with shift registers by using a bi-directional shift register. The register is shifted one way when data is inserted, and the other way when data is read out. However, the FIFO/LIFO designs which use shift registers require miore power than those which use RAM circuitry.
U.S. Pat. No. 4,592,019, issued May 27, 1986 to Alan Huang et al, discloses a system that overcomes the above problems by using a modular FIFO/LIFO design which has distributed control. Each memory cell independently determines its own occupancy status and position in a data list by using the occupancy status information from itself and from adjacent memory cells. With this information, a memory cell can determine whether it is at the head of a list, in the middle of a list, or at the tail of the list. Armed with this knowledge, each memory cell can determine whether it should respond or not respond to a read or write command.
In certain applications there is an increasing need for FIFO/LIFO memories having a more complete and an asynchronous access not only to data at the head or tail of a data list, as in Huang et al, but also to any of the data items stored in the list. It is an object of this invention to satisfy this need.